import java.util.PriorityQueue;

/**
 * 二维矩阵 grid 由 0 （土地）和 1 （水）组成。岛是由最大的4个方向连通的 0 组成的群，封闭岛是一个 完全 由1包围（左、上、右、下）的岛。
 *
 * 请返回 封闭岛屿 的数目
 * 题解：https://labuladong.gitee.io/algo/4/31/108/
 */
class ClosedIsland {
    public int closedIsland(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        for(int i=0;i<m;i++) {
            dfs(grid,i,0);
            dfs(grid,i,n-1);
        }
        for(int j=0;j<n;j++) {
            dfs(grid,0,j);
            dfs(grid,m-1,j);
        }
        int res = 0;
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(grid[i][j]==0) {
                    res++;
                    dfs(grid,i,j);
                }
            }
        }
        return res;
    }
    public void dfs(int[][] grid,int i,int j) {
        int m=grid.length;
        int n=grid[0].length;
        if(i<0||j<0||i>=m||j>=n||grid[i][j]==1) {
            return;
        }
        grid[i][j]=1;
        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1);
    
    }
}